//给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
//
// 假设二叉树中至少有一个节点。
//
//
//
// 示例 1:
//
//
//
//
//输入: root = [2,1,3]
//输出: 1
//
//
// 示例 2:
//
//
//
//
//输入: [1,2,3,4,null,5,6,null,null,7]
//输出: 7
//
//
//
//
// 提示:
//
//
// 二叉树的节点个数的范围是 [1,104]
// -231 <= Node.val <= 231 - 1
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树
// 👍 547 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.LinkedList;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxDepth = Integer.MIN_VALUE;  //全局变量  记录最大深度
    int result;  //全局变量最大深度最左节点的数值
    public int findBottomLeftValue(TreeNode root) {
        // 思路：层序遍历每一层只取出第一个元素然后赋值给res即可.
        /*Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (i == 0) {
                    res = poll.val;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return res;*/

        //法二：递归法怎么做？
        traversal(root, 0);
        return result;
    }
    void traversal(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            if (depth > maxDepth) {
                maxDepth = depth;  // 更新最大深度
                result = root.val;  // 最大深度最左边的数值
            }
            return;
        }
        if (root.left != null) {
            depth++;  //深度加一
            traversal(root.left, depth);
            depth--;  //深度减一
        }
        if (root.right != null) {
            depth++;  //深度加一
            traversal(root.right, depth);
            depth--;  //深度减一
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
